#define MAXSIZE 20      // 顺序表的最大长度
typedef int KeyType;    // 定义关键字类型为整型
typedef string InfoType;

typedef struct {
    KeyType key;
    InfoType otherinfo; // 其他数据项
} RedType;              // 记录类型

typedef struct {
    RedType r[MAXSIZE+1];   // r[0]闲置或用作哨兵单元
    int length;         // 顺序表长度
}SqList;                // 顺序表类型

void InsertSort(SqList &L) {
    int i, j;
    for (i = 2; i <= L.length; ++i) {
        if (L.r[i].key < L.r[i-1].key) {    // 若 " < ", 需将L.r[i]插入有序子表
            L.r[0] = L.r[i];        //  复制为哨兵
            for (j = i-1; L.r[0].key < L.r[j].key; --j) {
                L.r[j+1] = L.r[j];      // 记录后移
            }
            L.r[j+1] = L.r[0];      // 插入到正确位置
        }
    }
}